#include <iostream>
#include <string>

using namespace std;

int nextarr[100];

int kmp(string src, string pattern)
{
    int slen = src.length();
    int plen = pattern.length();

    int i = 0, j = 0;
    while(i < slen && j < plen)
    {
        if (-1 == j || src[i] == pattern[j])
        {
            ++i;++j;
        }
        else
        {
            j = nextarr[j];
        }
    }
    
    if(j >= plen)
    {
        return i - plen;
    }
    else
    {
        return -1;
    }

    return 0;
}

void getNext(string pattern)
{
    int i = 0, j = -1;
    nextarr[0] = -1;
    while(i < pattern.length())
    {
        if (-1 == j || pattern[i] == pattern[j])
        {
            ++i;++j;
            nextarr[i] = j;
        }
        else
        {
            j = nextarr[j];
        }
    }
}

int main(int argc, char *argv[])
{
    string src = "aaabc";
    string pattern = "abc";
    getNext(pattern);
    int i = kmp(src, pattern);
    cout << i << endl;
    return 0;
}
